#Basic pair of function based on the inductive proof.
#Too many functions, it must be shortened.

def ternary_tuple(n):
	"""
	Computes the number of ternary sequences ending with 0, 1 and 2.
	The result is stored in a tuple to compute it recursively.
	>>> print ternary_tuple(1)
	(1, 1, 0)
	>>> print ternary_tuple(2)
	(1, 2, 1)
	>>> print ternary_tuple(3)
	(3, 4, 2)
	"""
	if n == 1:
		return (1, 1, 0)
	else:
		(x, y, z) = ternary_tuple(n-1)
		return (y+z, x+y+z, y)

def ternary(n):
	"""
	Computes the total number of ternary sequences of the given length.
	>>> print ternary(0)
	1
	>>> print ternary(1)
	2
	>>> print ternary(2)
	4
	>>> print ternary(3)
	9
	"""
	if n == 0: 
		return 1 #empty
	else:
		return sum(ternary_tuple(n))

#Iterative version of ternary_tuple, simply added the n=0 case and computed the sum.

def ternary_it(n):
	"""
	Computes the total number of ternary sequences of the given length.
	>>> print ternary_it(0)
	1
	>>> print ternary_it(1)
	2
	>>> print ternary_it(2)
	4
	>>> print ternary_it(3)
	9
	"""
	if n == 0:
		return 1 #empty
	else:
		(x, y, z) = (1, 1, 0)
		while n != 1:
			(x, y, z) = (y+z, x+y+z, y)
			n -= 1
		return x+y+z

#Recursive version of ternary_it, added parameters with a default value.

def ternary_rec(n, x=1, y=1, z=0):
	"""
	Computes the total number of ternary sequences of the given length.
	>>> print ternary_rec(0)
	1
	>>> print ternary_rec(1)
	2
	>>> print ternary_rec(2)
	4
	>>> print ternary_rec(3)
	9
	"""
	if n == 0:
		return 1 #empty
	elif n == 1:
		return x+y+z
	else:
		return ternary_rec(n-1, y+z, x+y+z, y)

#Just to be sure it works well...

import doctest
doctest.testmod()
